from utils.array_utils import check_all


# merge sort


def merge_sort(ints):
    if len(ints) == 1:
        return ints
    mid_index = len(ints) // 2
    return merge(merge_sort(ints[:mid_index]), merge_sort(ints[mid_index:]))


def merge(left, right):
    l = r = 0
    t_list = []
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            t_list.append(left[l])
            l += 1
        else:
            t_list.append(right[r])
            r += 1
    t_list += left[l:]
    t_list += right[r:]
    return t_list


if __name__ == '__main__':
    arr = [5, 5, 8, 1, 8, 9, 9]
    arr = [-97, -69, 48, -88, -4, 53, 5, -4, 0]
    print(merge_sort(arr))
    print(check_all(merge_sort, 1000))
